package someTestExcemple.huaweiOd.sort;
//华为OD机试 - 考古问题 - 回溯、全排列问题（Java 2024 C卷 200分）
//https://blog.csdn.net/guorui_java/article/details/137026635
import java.util.*;
/*一、题目描述
        考古问题，假设以前的石碑被打碎成了很多块，每块上面都有一个或若干个字符，请你写个程序来把之前石碑上文字可能的组合全部写出来，按升序进行排列。

        二、输入描述
        若干个字符。

        三、输出描述
        把之前石碑上文字可能的组合全部写出来，按升序进行排列。

        1、输入
        3
        a b c

        2、输出
        abc
        acb
        bac
        bca
        cab
        cba*/
public class ArrangementOfText {
    private static  List<String> result = new ArrayList<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n =  Integer.parseInt(sc.nextLine());
        String[] arr = sc.nextLine().split("\\s");
        sc.close();
        List<String> list = Arrays.asList(arr);
        boolean[] visited = new boolean[n];

        dfs(list,n,visited,new StringBuilder());
        Collections.sort(result);
        for(String s : result) {
            System.out.println(s);
        }
    }
    public static void dfs(List<String> list,int n,boolean[] visited,StringBuilder sb) {
        if(sb.length() == n) {
            result.add(String.valueOf(sb));
            return;  //完整的排列，递归结束
        }
        for(int i=0;i<n;i++) {
            if(!visited[i]) {
                sb.append(list.get(i));
                visited[i] =true;
                dfs(list,n,visited,sb);
                //回溯 -要在这个if里面进行回溯
                visited[i] = false;
                sb.deleteCharAt(sb.length()-1);
            }


        }

    }

}
